/*
 * @lc app=leetcode.cn id=216 lang=cpp
 *
 * [216] 组合总和 III
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    void combin(set<vector<int>> &ans_vec,
                array<bool, 10> &vis,
                int start,
                const int k,
                const int n)
    {
        {
            int sum = 0;
            int visited = 0;

            for (int i = 1; i < 10; i++)
            {
                if (vis[i])
                {
                    sum += i;
                    visited++;
                }
            }
            if (visited == k)
            {
                if (sum == n)
                {
                    vector<int> ans;
                    for (int i = 1; i < 10; i++)
                    {
                        if (vis[i])
                        {
                            ans.push_back(i);
                        }
                    }
                    ans_vec.insert(ans);
                }
            }
            if(sum >= n || visited >= k || sum + start > n) return;
        }

        for (size_t i = start; i <= 9; i++)
        {
            vis[i] = true;
            combin(ans_vec, vis, i + 1, k, n);
            vis[i] = false;
            combin(ans_vec, vis, i + 1, k, n);
        }
    }

    vector<vector<int>> combinationSum3(int k, int n)
    {
        array<bool, 10> vis;
        for(auto& b : vis) b = false;
        set<vector<int>> ans_vec;
        combin(ans_vec, vis, 1, k, n);

        vector<vector<int>> ans;
        for(auto& v : ans_vec)
            ans.push_back(v);
        return ans;
    }
};

// int main(int argc, char const *argv[])
// {
//     Solution s;
//     s.combinationSum3(3, 7);
//     return 0;
// }


// @lc code=end
